package algorithm.difficult;


/**
 * @author 江岸
 * @version V1.0
 * @ClassName: SubarraysWithKDistinct992
 * @description: 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
 *
 * （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
 *
 * 返回 A 中好子数组的数目。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/2/9 14:00
 * @since V1.0
 */
public class SubarraysWithKDistinct992 {
    public static void main(String[] args) {

        System.out.println(subarraysWithKDistinct2(new int[]{1,2,1,2,3},2));
    }

    //双指针，如果数字超额，则左指针++，右指针回滚到左指针位置 自己写的会超时
    public static int subarraysWithKDistinct(int[] A, int K) {
        //出现的数字放入进去,num记数
        int[] frq = new int[A.length + 1];
        int num = 0;
        int left=0;
        int right=0;
        int count=0;
        while(right<=A.length){
            if (right==A.length){
                left++;
                right=left;
                frq = new int[A.length + 1];
                num = 0;
                continue;
            }
            if (frq[A[right]]==0){
                num++;
            }
            frq[A[right]]++;
            if (num<K){
                //数字还未装满
                right++;
                continue;
            }else if(num==K){
                //此时刚好装满
                count++;
                right++;
            }else if(num>K){
                left++;
                right=left;
                frq = new int[A.length + 1];
                num = 0;
            }
        }
        return count;
    }


    //恰好由 K 个不同整数的子数组的个数 = 最多由 K 个不同整数的子数组的个数 - 最多由 K - 1 个不同整数的子数组的个数
    public static int  subarraysWithKDistinct2(int[] A, int K) {
        return fun(A,K)-fun(A,K-1);
    }


    //求最多有K个不同整数的子数组
    //类似动态规划的思想，以右端点为基准 res = res + (right-left+1)
    public static  int fun(int[] A, int K){
        int[] frq = new int[A.length + 1];
        int num = 0;
        int left=0;
        int right=0;
        int res=0;
        while(right<A.length){
            if (frq[A[right]]==0){
                num++;
            }
            frq[A[right]]++;
            while (num>K){
                frq[A[left]]--;
                if ( frq[A[left]]==0){
                    num--;
                }
                left++;
            }
            //数字还未装满
            res = res + (right - left + 1);
            right++;

        }
        return res;
    }

}
